package com.sunny.l52;

public class Solution {

    public static void main(String[] args) {

        String s1 = "ab";
        String s2 = "bc";
        String s3 = "bcab";
        Solution solution = new Solution();
        solution.isInterleave(s1, s2, s3);

    }

    public boolean isInterleave(String s1, String s2, String s3) {
        if(null == s1 && null == s2){
            if(null == s3){
                return true;
            }
            return false;
        }
        if(null == s1 || "".equals(s1))
            return s2.equals(s3);
        if(null == s2 || "".equals(s2))
            return s1.equals(s3);
        if(s1.length() + s2.length() != s3.length())
            return false;

        boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];

        dp[0][0] = true;
        for(int i=1;i<=s1.length();i++){
            dp[i][0] = s1.charAt(i-1)==s3.charAt(i-1) && dp[i-1][0];
        }
        for(int j=1;j<=s2.length();j++){
            dp[0][j] = s2.charAt(j-1)==s3.charAt(j-1) && dp[0][j-1];
        }

        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=s2.length();j++){
                if(s3.charAt(i+j-1) == s1.charAt(i-1))
                    dp[i][j] = dp[i][j] || dp[i-1][j];
                if(s3.charAt(i+j-1) == s2.charAt(j-1))
                    dp[i][j] = dp[i][j] || dp[i][j-1];
            }
        }

//        for(int i=0;i<=s1.length();i++){
//            for(int j=0;j<=s2.length();j++){
//                System.out.print(dp[i][j]+" ");
//            }
//            System.out.println();
//        }

        return dp[s1.length()][s2.length()];
    }


}